package com.shangguigu.recursive.exc;

/**
 * @author: ZhouBert
 * @date: 2019/10/13
 * @description:	8 皇后
 * todo:有两个难点：1.如何回溯（在迷宫问题中，回溯是通过if判断回调自身实现，但是放在八皇后怎么处理呢？）；2.如何判断合法
 */
public class Queue8 {

	/**
	 * 皇后数量
	 */
	int max=8;
	/**
	 * todo:简化为用一维数组表示皇后的位置
	 */
	int[] arr=new int[max];

	int count=0;

	/**
	 *
	 * @return
	 */
	public int deal(){

		///答案个数
		int ans=0;
		///1.生产数字,用于放入结果数组的对应索引上
		for (int i = 0; i < max; i++) {

			for (int j = 0; j < max; j++) {
				if (i==j){
					continue;
				}else {

					if (judeg(i)){
						arr[j]=i;
					}

				}

			}
		}
		return 1;
	}

	public Queue8(){

	}

	/**
	 * 构建n皇后
	 * @param num
	 */
	public Queue8(int num){
		max=num;
		arr=new int[max];
	}

	/**
	 * 放置第n 个皇后
	 * @param n
	 * @return
	 */
	public void check(int n){
		if (n==max){
			count++;
			return ;
		}
		///todo:这个写法确实厉害啊！实现进位
		///依次放入皇后，判断是否冲突
		for (int i = 0; i < max; i++) {
			///先把当前这个皇后n,放到该行的第一列
			arr[n]=i;
			///判断当防止第n个皇后到i列时是否冲突
			///不冲突
			if (judeg(n)){
				///接着放n+1个皇后，开始递归
				check(n+1);
			}
			///如果冲突，继续执行array[n]=i;即将第n个皇后，放置在本行后移一个位置

		}
	}

	/**
	 * 当放置第n个皇后后，检测该皇后是否与之前已经摆放的皇后冲突
	 * todo:关键如何判断斜对角！——通过与之前每个位置判断行距和列距是否相等
	 * @param n
	 * @return
	 */
	private boolean judeg(int n){
		for (int i = 0; i < n; i++) {
			if (arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[i]-arr[n])){
				return false;
			}
		}
		return true;
	}


	public static void main(String[] args) {
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.printf("一共有%d 解法",queue8.count);

		Queue8 queue4 = new Queue8(4);
		queue4.check(0);
		System.out.printf("一共有%d 解法",queue4.count);
	}

}
